/**
 * 我和冰冰贴贴
 * voyagerhui
 * 0316
 * 说明：总的思想是将服务器和虚拟机按照cpu/memory的值进行分类。
 *      对应的虚拟机只会和对应的服务器联系，
 *      相关的购买、部署、删除都是在一类中进行的。
 *      需要保证每个分类的服务器不同！
 */

// #define DEBUG 1
/******************* 头文件 *******************/
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

/******************* 结构体定义 *******************/
// 服务器类型信息
struct server_param{
    int cpu;            // CPU核数
    int memory;         // 内存大小
    int price;          // 硬件成本
    int cost;           // 每日能耗成本
    int index;          // 类别
    float ratio;        // cpu/mem
    float unit_price;   // 单位价格
    server_param(int a, int b, int c, int d, int e, float f, float g):cpu(a), memory(b), price(c), cost(d), index(e), ratio(f), unit_price(g) {}
    server_param():cpu(), memory(), price(), cost(), index(), ratio(), unit_price() {}
};
// 虚拟机类型信息
struct vm_param{
    int cpu;            // CPU核数
    int memory;         // 内存大小
    int two;            // 是否双节点部署 0:单节点 1:双节点
    int index;          // 类别
    float ratio;        // cpu/mem
    vm_param(int a, int b, int c, int d, float e):cpu(a), memory(b), two(c), index(d), ratio(e){}
    vm_param():cpu(), memory(), two(), index(), ratio() {}
};
// 一天的请求信息
struct request_day {
    int r;                  // 一天的请求数
    vector<char> ad;        // a: add  d:del
    vector<string> model;   // 虚拟机型号
    vector<int> id;         // 虚拟机ID
    request_day():r(0), ad({}), model({}), id({}) {}
};
// 一台服务器可用资源
struct server_mesg{
    int a_c;        // 节点a剩余cpu核数
    int a_m;        // 节点a剩余内存
    int b_c;        // 节点b剩余cpu核数
    int b_m;        // 节点b剩余内存
    string model;   // 服务器型号名
    server_mesg(int a, int b, int c, int d, string e):a_c(a), a_m(b), b_c(c), b_m(d), model(e){}
    server_mesg():a_c(), a_m(), b_c(), b_m(), model() {}
};
// 一个虚拟机对应信息
struct vm_mesg{
    string model;   // 虚拟机型号名
    int serverid;   // 部署的服务器id
    int servernode; // 部署节点 0: A节点 1: B节点 2: 双节点
    vm_mesg(string a, int b, int c):model(a), serverid(b), servernode(c){}
    vm_mesg():model(), serverid(), servernode() {}
};

/******************* 常量 *******************/
constexpr auto EIGHT = 8;

/******************* 全局变量 *******************/
float class_ratio[EIGHT] = {0.08, 0.28, 0.5, 0.8, 1, 1.2, 4, 7.5};  // 各个分类的中心ratio
float k[EIGHT][2] = {{0.0, 1.0},
                     {0.1, 0.9},
                     {0.2, 0.7},
                     {0.3, 0.6},
                     {0.5, 0.5},
                     {0.6, 0.4},
                     {0.8, 0.2},
                     {1.0, 0.0}};                   // 计算各个类别服务器单位价格时用到的权重

int N = 0, M = 0, T = 0, R = 0;                     // 服务器类型数、虚拟机类型数、天数、每天请求数
unordered_map<string, struct server_param> server;  // 全部服务器信息
unordered_map<string, struct vm_param> vm;          // 全部虚拟机信息
vector<request_day> request;                        // 请求队列

int idle_server_n = 0, server_n = 0, vm_n = 0;      // 空闲服务器数量、现存的服务器数量、现存的虚拟机数量
vector<struct server_mesg> server_resource;         // 服务器资源（索引为服务器id）
vector<int> server_task_count;                      // 计数服务器上虚拟机个数
vector<bool> server_priority_node;                  // 单节点时优先部署在a节点
unordered_map<int, struct vm_mesg> vm_message;      // 虚拟机id和型号、部署的服务器id、节点的映射关系
vector<string> class_server(EIGHT, "");             // 各类最优服务器型号

vector<string> ans;                                 // 存储打印内容
long long purchase_cost = 0, daily_cost = 0, all_cost = 0;  // 服务器购买花费、每日花费、总费用

/******************* 函数声明 *******************/
float computeUnitPrice(int cpu, int memory, int price, int cost);       // 计算服务器的单位价格
int getIndex(float ratio);                  // 返回服务器（或虚拟机）对应的类别
void findBestClassServer();                 // 寻找各个类别的最优的服务器
int tryDeploy(int vm_id, int server_id);    // 返回服务器可部署节点
int dealOneClassRequest(int index, int t, vector<string>& deploy_ans);  // 处理一类服务器的请求
void myAlgorithm();                         // 决策算法

void purchaseServer(string model, int num);                 // 购买服务器
void migrationVM(int vmID, int serverID, int serverNode);   // 迁移虚拟机
void deployVM(int vmID, int serverID, int serverNode);      // 部署虚拟机到服务器节点
void delVM(int vmID);       // 从服务器删除虚拟机
void readData();            // 读取stdin的数据


/******************* 函数 *******************/
/* 计算服务器的单位价格
 * 单位价格的计算公式与服务器的类别有关
 * 注意调节参数k
 */
float computeUnitPrice(int cpu, int memory, int price, int cost)
{
    float ratio = 1.0*cpu/memory;
    int index = getIndex(ratio);
    float tmp = k[index][0] * cpu + k[index][1] * memory;
    float unit_price = (0.7*price+6.0*cost)/tmp;  
    return unit_price;
}

/* 返回该ratio对应的类别编号
 * 根据中心频点进行划分
 */
int getIndex(float ratio)
{
    int index = 0;
    for(int i=0; i<EIGHT-1; ++i){
        if(ratio < 1.0*(class_ratio[i]+class_ratio[i+1])/2){
            index = i;
            break;
        }else{
            index = i+1;
        }
    }
    return index;
}

/* 寻找各个类别的最优的服务器
 * 满足该类所有虚拟机的最低配置
 * 单位价格最低的服务器
 */
void findBestClassServer()
{
    // 找出各类服务器需要的最低配置
    vector<int> bound_cpu(EIGHT, 0);
    vector<int> bound_mem(EIGHT, 0);
    for (unordered_map<string, struct vm_param>::iterator it = vm.begin(); it != vm.end(); ++it) {
        int index = it->second.index;
        int _required_cpu = it->second.cpu;
        int _required_mem = it->second.memory;
        if(it->second.two == 0){    // 虚拟机单节点部署
            _required_cpu *= 2;
            _required_mem *= 2;
        }
        bound_cpu[index] = bound_cpu[index] >= _required_cpu ? bound_cpu[index] : _required_cpu;
        bound_mem[index] = bound_mem[index] >= _required_mem ? bound_mem[index] : _required_mem;
    }
    // 找出各类服务器中的满足cpu和mem限制的服务器，并且单价尽可能低
    for (unordered_map<string, struct server_param>::iterator it = server.begin(); it != server.end(); ++it) {
        string model = it->first;
        int cpu = it->second.cpu;
        int memory = it->second.memory;
        float unit_price = it->second.unit_price;
        int index = it->second.index;
        if(cpu >= bound_cpu[index] && memory >= bound_mem[index]){
            if(class_server[index] == ""){
                class_server[index] = model;
            }else{
                if(unit_price < server[class_server[index]].unit_price){
                    class_server[index] = model;
                }
            }
        }
    }
    // 如果没有找到一个类别的最优的服务器，则尽量用相邻ratio的服务器来代替
    for(int i=0; i<EIGHT; ++i){
        if(class_server[i] == ""){            
            for (unordered_map<string, struct server_param>::iterator it = server.begin(); it != server.end(); ++it) {
                if(it->second.cpu >= bound_cpu[i] && it->second.memory >= bound_mem[i]){
                    if(class_server[i] == ""){
                        class_server[i] = it->first;
                    }else{
                        int old_ratio = server[class_server[i]].ratio;
                        int new_ratio = server[it->first].ratio;
                        if(abs(new_ratio-class_ratio[i]) < abs(old_ratio-class_ratio[i])){
                            class_server[i] = it->first;
                        }
                    }
                }
            }
        }
    }
}

/* 尝试部署
 * return: -1：不能部署，0：部署到a节点，1：部署到b节点，2：部署到双节点
 * 单节点部署时，如果两个单节点都可部署，选择优先部署节点
 */
int tryDeploy(int vm_id, int server_id)
{
    int server_node = -1;
    string vm_model = vm_message[vm_id].model;
    int _required_cpu = vm[vm_model].cpu;
    int _required_mem = vm[vm_model].memory;
    if(vm[vm_model].two == 1){     // 双节点部署
        _required_cpu /= 2;
        _required_mem /= 2;
        if(server_resource[server_id].a_c >= _required_cpu 
          && server_resource[server_id].a_m >= _required_mem
          && server_resource[server_id].b_c >= _required_cpu 
          && server_resource[server_id].b_m >= _required_mem){
            server_node = 2;
        }
    }else{      // 单节点部署
        bool node_a = server_resource[server_id].a_c >= _required_cpu && server_resource[server_id].a_m >= _required_mem;
        bool node_b = server_resource[server_id].b_c >= _required_cpu && server_resource[server_id].b_m >= _required_mem;
        if(node_a && node_b){   // 两个单节点都可部署时选择优先节点
            if(server_priority_node[server_id]){
                server_node = 0;
            }else{
                server_node = 1;
            }
        }else if(node_a){   // 选择a节点
            server_node = 0;
        }else if(node_b){   // 选择b节点
            server_node = 1;
        }
    }
    return server_node;
}

/* 处理一类的请求
 * 返回值：该类需要新购服务器的数量
 * index: 服务器类别编号
 * t：天数
 * deploy_ans：部署过程的输出
 */
int dealOneClassRequest(int index, int t, vector<string>& deploy_ans)
{
    int n = 0;
    string target_model = class_server[index];     // 本类新购服务器类型 

    for(int i=0; i<request[t].r; ++i){
        int vm_id = request[t].id[i];
        string vm_model = request[t].model[i];
        // 只处理类别为index的请求
        if(vm[vm_model].index != index){
            continue;
        }
        if(request[t].ad[i] == 'd'){
            delVM(vm_id);
        }else{
            int server_id = -1;
            int server_node = -1;
            // 尝试在已有的服务器上部署
            for(int j=0; j<server_n; ++j){
                if(server_resource[j].model == target_model){
                    server_node = tryDeploy(vm_id, j);
                    if(server_node != -1){
                        server_id = j;  // 得到可以部署的服务器id
                        break;
                    }
                }
            }
            // 不够就买新的服务器
            if(server_node == -1){
                purchaseServer(target_model, 1);
                server_id = server_n-1;  // 得到可以部署的服务器id
                n++;
            }
            // 部署
            server_node = tryDeploy(vm_id, server_id);     // 得到可以部署的服务器节点
            deployVM(vm_id, server_id, server_node);
            // 保存部署信息
            if(server_node == 2){
                deploy_ans[i] = "(" + to_string(server_id) + ")";
            }else if(server_node == 0){
                deploy_ans[i] = "(" + to_string(server_id) + ", A)";
            }else if(server_node == 1){
                deploy_ans[i] = "(" + to_string(server_id) + ", B)";
            }else{
                cout << "ERROR in dealOneClassRequest, server_node:" << server_node << "\n";
                exit(1);
            }
        }
    }
    return n;
}

/* 决策算法
 * 购买-迁移-部署-结算
 * 分类别处理请求，虚拟机的部署、删除、服务器的购买都是是同类间处理
 */
void myAlgorithm()
{
    findBestClassServer();    // 找出各类最优服务器
    for(int t=0; t<T; ++t){
        int Q = 0;
        int r = request[t].r;
        vector<string> deploy_ans(r, "");
        vector<int> purchase_num(EIGHT, 0);
        // 分类别处理请求
        for(int i=0; i<EIGHT; ++i){
            purchase_num[i] = dealOneClassRequest(i, t, deploy_ans);
            if(purchase_num[i] > 0){
                Q++;
            }
        }
        // 整理一天的输出
        ans.push_back("(purchase, "+to_string(Q)+")");
        for(int i=0; i<EIGHT; ++i){
            if(purchase_num[i] > 0){
                ans.push_back("("+class_server[i]+", "+to_string(purchase_num[i])+")");
            }
        }
        ans.push_back("(migration, 0)");
        for(int i=0; i<r; ++i){
            if(deploy_ans[i] != ""){
                ans.push_back(deploy_ans[i]);
            }
        }
        // 结算每日费用
        for(int i=0; i<server_n; ++i){
            if(server_task_count[i] > 0){
                daily_cost += server[server_resource[i].model].cost;
            }
        }
    }
    all_cost = purchase_cost + daily_cost;
}

/* 购买服务器
 * 将购买的服务器加入server_resource中，索引就是服务器ID
 */
void purchaseServer(string model, int num)
{
    if(num <= 0){
        cout << "ERROR! purchaseServer num=" << num << "\n";
        exit(1);
    }

    for (int i = 0; i < num; ++i){
        struct server_mesg tmp(server[model].cpu/2, server[model].memory/2, 
                                          server[model].cpu/2, server[model].memory/2, model);
        server_resource.push_back(tmp);     // 加入服务器资源列表
        server_task_count.push_back(0);     // 当前服务器部署虚拟机个数
        server_priority_node.push_back(true);   // 当前服务器最近单节点部署在a节点还是b节点
    }
    idle_server_n += num;
    server_n += num;
    purchase_cost += static_cast<long long>(num)*(server[model].price);
}

/* 迁移虚拟机
 * 1.从原服务器删除虚拟机
 * 2.将虚拟机部署到新服务器的新节点
 */
void migrationVM(int vmID, int serverID, int serverNode)
{
    delVM(vmID);
    deployVM(vmID, serverID, serverNode);
}

/* 部署虚拟机到服务器
 * 1.改变服务器资源
 * 2.维护虚拟机和服务器之间的映射关系
 * 3.修改相应标志位
 * 部署前一定调用tryDeploy()保证部署成功
 */
void deployVM(int vmID, int serverID, int serverNode)
{
    if (serverID < 0 || serverNode < 0) {
        cout << "ERROR! serverID:" << serverID << " vmID:" << vmID << " serverNode:" << serverNode << "\n";
        exit(1);
    }

    string model = vm_message[vmID].model;
    vm_message[vmID].serverid = serverID;
    vm_message[vmID].servernode = serverNode;
    if (serverNode == 2) {     // 双节点部署
        server_resource[serverID].a_c -= (vm[model].cpu/2);
        server_resource[serverID].a_m -= (vm[model].memory/2);
        server_resource[serverID].b_c -= (vm[model].cpu/2);
        server_resource[serverID].b_m -= (vm[model].memory/2);
    } else if (serverNode == 0) {     // a节点部署
        server_resource[serverID].a_c -= (vm[model].cpu);
        server_resource[serverID].a_m -= (vm[model].memory);
        server_priority_node[serverID] = false;
    } else {    // b节点部署
        server_resource[serverID].b_c -= (vm[model].cpu);
        server_resource[serverID].b_m -= (vm[model].memory);
        server_priority_node[serverID] = true;
    }
    vm_n++;
    if(server_task_count[serverID] == 0){
        idle_server_n--;
    }
    server_task_count[serverID]++;
}

/* 删除虚拟机
 * 1.改变服务器资源
 * 2.维护虚拟机和服务器之间的映射关系
 * 3.修改相应标志位
 */
void delVM(int vmID)
{
    string model = vm_message[vmID].model;
    int serverID = vm_message[vmID].serverid;
    int serverNode = vm_message[vmID].servernode;
    if (serverID < 0 || serverNode < 0) {
        cout << "ERROR! DEL ERROR, serverID:" << serverID << " vmID:" << vmID << "\n";
        exit(1);
    }

    vm_message[vmID].serverid = -1;
    vm_message[vmID].servernode = -1;
    if (serverNode == 2) {     // 双节点部署
        server_resource[serverID].a_c += (vm[model].cpu/2);
        server_resource[serverID].a_m += (vm[model].memory/2);
        server_resource[serverID].b_c += (vm[model].cpu/2);
        server_resource[serverID].b_m += (vm[model].memory/2);
    } else if (serverNode == 0) {     // a节点部署
        server_resource[serverID].a_c += (vm[model].cpu);
        server_resource[serverID].a_m += (vm[model].memory);
        server_priority_node[serverID] = true;
    } else {    // b节点部署
        server_resource[serverID].b_c += (vm[model].cpu);
        server_resource[serverID].b_m += (vm[model].memory);
        server_priority_node[serverID] = false;
    }
    vm_n--;
    server_task_count[serverID]--;
    if(server_task_count[serverID] == 0){
        idle_server_n++;
    }
}

/* 读取并解析数据
 * 将服务器、虚拟机、请求信息存入全局变量
 */
void readData()
{
    string s_0, s_1, s_2, s_3, s_4;
    int i_1, i_2, i_3, i_4, i_5;
    float f_0, f_1;
    // 读取服务器信息
    cin >> N;
    for (int i = 0; i < N; ++i) {
        cin >> s_0 >> s_1 >> s_2 >> s_3 >> s_4;
        string s = s_0.substr(1, s_0.size() - 2);
        i_1 = atoi(s_1.substr(0, s_1.size() - 1).c_str());
        i_2 = atoi(s_2.substr(0, s_2.size() - 1).c_str());
        i_3 = atoi(s_3.substr(0, s_3.size() - 1).c_str());
        i_4 = atoi(s_4.substr(0, s_4.size() - 1).c_str());
        f_0 = 1.0*i_1 / i_2;  // cpu/mem
        i_5 = getIndex(f_0);  // index
        f_1 = computeUnitPrice(i_1, i_2, i_3, i_4);
        struct server_param server_param_tmp(i_1, i_2, i_3, i_4, i_5, f_0, f_1);
        server[s] = server_param_tmp;
    }
    // 读取虚拟机信息
    cin >> M;
    for (int i = 0; i < M; ++i) {
        cin >> s_0 >> s_1 >> s_2 >> s_3;
        string s = s_0.substr(1, s_0.size() - 2);
        i_1 = atoi(s_1.substr(0, s_1.size() - 1).c_str());
        i_2 = atoi(s_2.substr(0, s_2.size() - 1).c_str());
        i_3 = atoi(s_3.substr(0, s_3.size() - 1).c_str());
        f_0 = 1.0*i_1/i_2;      // cpu/mem
        i_4 = getIndex(f_0);    // index
        struct vm_param vm_param_tmp(i_1, i_2, i_3, i_4, f_0);
        vm[s] = vm_param_tmp;
    }
    // 读取每天的请求信息
    cin >> T;
    for (int i = 0; i < T; ++i) {
        cin >> R;
        struct request_day request_day_tmp;
        request_day_tmp.r = R;
        for (int j = 0; j < R; ++j) {
            cin >> s_0;
            if (s_0[1] == 'a') {    // add
                cin >> s_1 >> s_2;
                string s = s_1.substr(0, s_1.size() - 1);
                i_1 = atoi(s_2.substr(0, s_2.size() - 1).c_str());
                request_day_tmp.ad.push_back('a');
                request_day_tmp.model.push_back(s);
                request_day_tmp.id.push_back(i_1);
                struct vm_mesg vm_mesg_tmp(s, -1, -1);
                vm_message[i_1] = vm_mesg_tmp;
            } else {  // del
                cin >> s_1;
                i_1 = atoi(s_1.substr(0, s_1.size() - 1).c_str());
                string s = vm_message[i_1].model;
                request_day_tmp.ad.push_back('d');
                request_day_tmp.model.push_back(s);     // 补全请求中del时的型号信息
                request_day_tmp.id.push_back(i_1);
            }
        }
        request.push_back(request_day_tmp);
    }
}


int main()
{
#ifdef DEBUG
    char* filePath = (char*)"training-2.txt";
    freopen(filePath, "rb", stdin);
    readData();
    myAlgorithm();
    cout << "purchase_cost:" << purchase_cost << " daily_cost:" << daily_cost << " all_cost:" << all_cost << "\n";
    cout << "server_n:" << server_n << " vm_n:" << vm_n << " idle_server_n:" << idle_server_n << "\n";
    ofstream outputfile;
    outputfile.open("ans.txt");
    for (const string& s : ans) {
        outputfile << s << "\n";
    }
    outputfile.close();
#else
    readData();
    myAlgorithm();
    for (const string& s : ans) {
        cout << s << "\n";
    }
    fflush(stdout);
#endif
    return 0;
}
